package leetcode;

//不相邻元素的最大和
public class NoAdjacentElementMaxSum {
	
	//思路主要就是记录两个变量，一个exclude，一个include
	//exclude表示不包括当前元素的最大和
	//include表示包括当前元素的最大和
	//exclude[i + 1] = Max(exclude[i], include[i]) 
	//include[i + 1] = exclude[i] + nums[i + 1]  //因为是非负的整数
	//http://www.geeksforgeeks.org/maximum-sum-such-that-no-two-elements-are-adjacent/
	public int rob(int[] nums) {
        if(nums == null || nums.length <= 0){
            return 0;
        }
        int exclude = 0;  //不包含当前元素的最大值
        int exclude_new ;   //更新后的exclude值
        int include = nums[0];  //包含当前元素时的最大值
        int maxSum = 0;
        for(int i = 1; i < nums.length; i++){
            //由于exclude_new是指的不包括当前元素的最大值，所以就等于前一个元素的ex和in中的最大值
            exclude_new = Math.max(exclude, include);  
            include = exclude + nums[i];   //等于不包含前一个元素的最大值 + nums[i](注意，是非负的整数)
            exclude = exclude_new;
        }
        maxSum = Math.max(exclude, include);
        return maxSum;
    }
}
